package com.leetcode.algorithm.y22.m07;

import java.util.ArrayList;
import java.util.List;

/**
 * 784. 字母大小写全排列
 * 
 * https://leetcode.cn/problems/letter-case-permutation/
 * 
 * @author jie.deng
 *
 */
class Question0784Solution02 {

	public List<String> letterCasePermutation(String s) {
		List<String> list = new ArrayList<>();
		char[] data = s.toCharArray();
		letterCasePermutation(0, data, list);
		return list;
	}

	private void letterCasePermutation(int idx, char[] data, List<String> retList) {
		int len = data.length;
		// 递归终止条件
		if (idx == len) {
			retList.add(String.valueOf(data));
			return;
		}

		// 当前层逻辑
		char ch = data[idx];
		if (ch <= '9') {
			// 递归调用下一层
			letterCasePermutation(idx + 1, data, retList);
		} else {
			if (ch >= 'a') {
				// 递归调用下一层
				letterCasePermutation(idx + 1, data, retList);

				// 回溯
				data[idx] = (char) (ch - 32);
				letterCasePermutation(idx + 1, data, retList);
				data[idx] = ch;
			} else {
				// 递归调用下一层
				letterCasePermutation(idx + 1, data, retList);

				// 回溯
				data[idx] = (char) (ch + 32);
				letterCasePermutation(idx + 1, data, retList);
				data[idx] = ch;
			}
		}
	}

}